package leetcode.code0140;

import java.util.ArrayList;
import java.util.List;

public class Solution3 extends Solution140 {

	Node root;
	List<String> ans;
	int Len;

	class Node {

		Node[] characters;

		boolean isEnd;

		public Node() {
			this.characters = new Node[26];
		}

		public void add(String word) {
			Node node = root;
			for (int i = 0; i < word.length(); i++) {
				int index = word.charAt(i) - 'a';
				if (node.characters[index] == null) {
					node.characters[index] = new Node();
				}
				node = node.characters[index];
			}
			node.isEnd = true;
		}
	}

	@Override
	public List<String> wordBreak(String s, List<String> wordDict) {
		this.Len = s.length();
		this.root = new Node();
		for (String word : wordDict) {
			root.add(word);
		}
		this.ans = new ArrayList<>();
		char[] string = s.toCharArray();
		StringBuffer temp = new StringBuffer();
		String[] dp = new String[this.Len];
		this.f(string, 0, temp);
		return ans;
	}

	private void f(char[] string, int index, StringBuffer temp) {
		if (index == this.Len) {
			ans.add(temp.toString());
			return;
		}
		Node node = root;
		for (int i = index; i < this.Len; i++) {
			int c = string[i] - 'a';
			if (node.characters[c] == null) {
				return;
			} else {
				node = node.characters[c];
				if (node.isEnd) {
					if (temp.length() != 0) {
						temp.append(' ');
					}
					temp.append(new String(string, index, i - index + 1));
					this.f(string, i + 1, temp);
					temp.delete(index, temp.length());
				}
			}
		}
	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
